An example of a conventional network configuration is shown in FIG. 5. As shown in FIG. 5, the network is composed of nodes (11, 12, . . . , 15 in the figure) and links (21, 22, . . . , 26 in the figure). A communication route which passes through a plurality of nodes and links and which is terminated by a pair of nodes is called a "path". Each node is a junction on a path or terminates a path, and each link accommodates one or more paths (i.e., a link is a part through which a path passes).
In FIG. 5, path 33 is terminated by nodes 11 and 13 and junctioned by node 12. At the same time, path 33 is accommodated by links 21 and 22. A pair of nodes terminating a path is called a "demand pair."
In a normal state in which no failure is found in all the nodes and links of a network, a path used by a demand pair is called a "current path." For example, in FIG. 5, path 31 is the current path of the demand pair composed of nodes 11 and 13.
When a failure occurs in a node or a link, the demand pair whose current path is affected by the failure switches the current path to a path called a "standby path (or spare path)." For example, in FIG. 5, the demand pair composed of nodes 11 and 13 has two standby paths: path 32 and path 33. When the current path 31 is affected by a failure, path 32 or path 33 is used as a standby path.
It should be noted that each path is associated with two factors: one is the route to be defined by the sequence of nodes and links between the two nodes of a demand pair, and another is the "capacity." And, if a link can accommodate a path with a capacity c, it implies that the link has a vacant capacity of c.
For a demand pair affected by a network failure to have a standby path, the capacity required for the current path and the capacity required for the standby path must be allocated to the link.
A conventional network design method aims at determining the topology of a network composed of nodes and links, the demand capacity of a demand pair, the capacity to be allocated to each link and the path route of each demand pair when a failure pattern is given.
For example, "Robust Traffic Design for Dynamic Routing Networks" (IEEE proceedings of INFOCOM'91, 1991, pp. 508-514) describes a method which determines a path ensuring a minimized cost of link capacity, when a network failure occurs under the condition that each link can accommodate a path which will be used by each demand pair.
The following symbols are used to formulate this problem.
First, numbers are assigned as follows:
l=1, . . . , L: Number assigned to a link PA1 m=1, . . . , M: Number assigned to a demand pair PA1 i.sub.m =1, . . . , I.sub.m : Number assigned to a path candidate that will be used by demand pair m PA1 s=0: Number assigned to a normal state of a network PA1 s=1, . . . , S: Number assigned to each failure state of a network. PA1 .omega.: Link capacity augmentation unit (for example, a transmission capacity per fiber optic cable) PA1 a.sub.1 : Cost of capacity augmentation unit .omega. for link 1 PA1 g.sub.im.sup.1 : Indicator assuming "1" when path i.sub.m is accommodated by link 1; "0" when path i.sub.m is not accommodated by link 1. PA1 v.sub.m.sup.s : Capacity requested by demand pair m in a network state s PA1 i.sub.m.sup.0 : Current path used by demand pair m PA1 d.sub.1.sup.0 : Number of capacity augmentation units required for link 1 to accommodate the current path of each demand pair. In this case, the total capacity of link 1 is given as .omega. d.sub.1.sup.0. PA1 c.sub.im.sup.s : Capacity allocated to path im in the state s. PA1 d.sub.1 : Number of capacity augmentation units for link 1. The total capacity of a link is given as .omega. d.sub.1. The cost of link 1 is given as a.sub.1 d.sub.1. PA1 providing a plurality of combination candidates of a first to an N-th path for a demand pair composed of a pair of the nodes, N being an integer of at least 2 and said demand pair having a demand capacity; PA1 solving a mathematical programming problem. The mathematical programming problem comprises objective functions which comprises: PA1 a capacity to be assigned to the current path accommodated by each of the links, when said current path is not affected by a failure on the network in the one or more time zones, in each of the directions, and in a normal state and each failure state of the network, PA1 a capacity to be assigned to the first standby path accommodated by said link, when the current path corresponding to the first standby path is affected by a failure on said network, PA1 a capacity to be assigned to said n-th (n=2, . . . , N-1) standby path accommodated by said link when the current path corresponding to the nth standby path and the first to (n-1)th standby paths are affected by a failure on the network, where N is an integer of at least 3, and PA1 a second constraint under which a total of the capacity of the current path accommodated by the link and capacities of the first standby path to (N-1)th standby path for the demand pair does not exceed a capacity assigned to the link. PA1 capacities to be assigned to each of the combination candidates for each of the demand pairs in one or more time zones and in each direction, each of the combination candidates being composed of a current path which is any one of a first to an N-th path and any one or more of first to (N-1)th standby paths corresponding to the current path, and PA1 a first constraint under which a total of capacities to be assigned to the current path satisfies the demand capacity of the demand pair in the one or more time zones and in each of the directions. PA1 capacities each to be assigned to the current path accommodated by the link when said current path is not affected by a failure on said network in the one or more time zones, in each of the directions, and in a normal state and a failure state of the network, PA1 a capacity to be assigned to the first standby path when the current path corresponding to the first standby path is affected by a failure on the network, PA1 a capacity to be assigned to the n-th (n=2, . . . , N-1) standby path accommodated by the link when the current path and the first to (n-1)th standby paths are affected by a failure on the network, where N is an integer of at least 3, and PA1 a second constraint under which a total of the capacities of the current path and any one of the first standby path to (N-1)th standby path for the demand pair does not exceed a capacity assigned to the link. PA1 (a) providing a network topology, a failure pattern specifying a location at which a failure occurs on the network, a demand capacity for a current path of a demand pair which is a pair of nodes, each terminating the path, in each time zone and in each direction and a demand pair for a standby path to be used when the current path is affected by the network failure, and combination candidates of a current path and a standby path in the each demand pair; PA1 (b) solving an integer programming problem having an objective function which minimizes a cost caused by the link capacity based on information given by the preceding steps, the objective function having: PA1 (c) determining, from a result of solution of the integer programming problem, link capacities as well as a current path and a standby path to be used by each demand pair in each time zone. PA1 the mixed integer programming problem further comprising a condition that the capacity to be assigned to the standby path is not less than the capacity value assigned to the current path multiplied by a request recovery ratio. By solving the mixed integer programming problem the capacity is assigned to the current path and the standby path in each time zone and for each demand pair.
Constants are defined as follows:
Variables are defined as follows:
Using the above symbols, the conventional network design method has solved the following linear programming problem to determine a path and its capacity to be used by each demand pair in each state:
A problem by which the values of variables for optimizing (minimizing or maximizing) an objective function, as well as the value generated by the objective function using those values, are obtained is called a "mathematical programming problem." The values of variables used in this problem are within a specific range of values satisfying a specific constraint. In particular, a mathematical programming problem in which an objective function and the constraint are expressed by variables in linear format is called a "linear programming problem."
To solve the following problem, it is necessary to give possible path candidates to each demand pair. This generates an indicator g.sub.im.sup.1. ##EQU1## EQU d.sub.l .gtoreq.d.sub.l.sup.0 (l=1, . . . ,L) (4) EQU c.sub.im.sup.s .gtoreq.0(s=1, . . . ,S, m=1, . . . ,M, i.sub.m =1, . . . ,I.sub.m) (5)
The above formula (1) shows that the total of the costs accompanying each link capacity is the objective function which is to be minimized.
The above formula (2) is a constraint representing that the total of the capacities of paths accommodated by each link does not exceed the total capacity of the link.
The above formula (3) is a constraint representing that the total of the capacities assigned to the paths to be used by each demand pair when a failure occurs is equal to or greater than the capacity requested by each demand pair in a network state s.